package cn.edu.ncepu;

import java.util.*;

public class CombinationGenerator {

    // 封装队列元素：当前组合 + 起始索引
    private static class QueueItem<T> {
        List<T> combination;
        int startIndex;

        public QueueItem(List<T> combination, int startIndex) {
            this.combination = combination;
            this.startIndex = startIndex;
        }
    }

    /**
     * 生成输入列表的所有组合（广度优先遍历）
     * @param input 原始列表
     * @return 所有组合的列表，顺序与Python版本一致
     * @param <T> 元素类型
     */
    public static <T> List<List<T>> combinations(List<T> input) {
        // 初始化队列，使用LinkedList实现Queue接口，模拟Python的列表队列
        Queue<QueueItem<T>> queue = new LinkedList<>();
        queue.offer(new QueueItem<>(new ArrayList<>(), 0));

        List<List<T>> result = new ArrayList<>();

        while (!queue.isEmpty()) {
            // 弹出队首元素（对应Python的pop(0)）
            QueueItem<T> item = queue.poll();
            List<T> currentComb = item.combination;
            int startIdx = item.startIndex;

            // 将当前组合加入结果
            result.add(currentComb);

            // 生成子组合：从startIdx开始遍历剩余元素
            List<T> subarray = input.subList(startIdx, input.size());
            for (int i = 0; i < subarray.size(); i++) {
                T child = subarray.get(i);
                // 构建新组合：拷贝当前组合并添加子元素
                List<T> newComb = new ArrayList<>(currentComb);
                newComb.add(child);
                // 计算新的起始索引：startIdx + i + 1
                int newStartIdx = startIdx + i + 1;
                // 将新的队列元素加入队列
                queue.offer(new QueueItem<>(newComb, newStartIdx));
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // 测试：生成['A','B','C']的所有组合
        List<String> input = Arrays.asList("A", "B", "C");
        List<List<String>> result = combinations(input);

        // 输出结果，格式与Python一致
        System.out.println(result);
    }
}